/*
* 最短路径+DP
* 

* spfa
* 从 1 走到 i 的过程中，买入水晶球的最低价格 dmin[i]；
* 从 i 走到 n 的过程中，卖出水晶球的最高价格 dmax[i]；
* 先求节点1到各个节点最小值，然后求节点n到各个节点的最大距离(反向)
* 在一个城市卖出水晶球的最好收益为：price[u] - dist[u] 当地的价格 - 走到 u (包括之前)遇见的最低价格
* 枚举每个城市作为买卖的中间城市，求出 dmax[i] - dmin[i] 的最大值即可
*/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
// #define ONLINE_GUDGE
using namespace std;
const int N = 100010, M = 2000010, INF = 0x3f3f3f3f;

int n, m; // n个节点 m条道路
int w[N];
int h[N], rh[N], e[M], ne[M], idx; // 道路

int dmin[N], dmax[N]; // 最小卖出价格 最大卖出价格
bool st[N];

void AddEdge(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa(int h[], int dist[],  bool type) // u==0表示求最小值，1最大值
{
    queue<int> q;
    // memset(st, 0, sizeof st);

    if (type == 0){
        memset(dist, 0x3f, sizeof dmin);
        dist[1] = w[1];
        q.push(1);
    } 
    else{
        memset(dist, -0x3f, sizeof dmin);
        dist[n] = w[n];
        q.push(n);
    }

    while(q.size())
    {
        auto u = q.front(); q.pop();

        // if(st[u]) continue;
        st[u] = false;

        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            //正搜求最小值，反搜求最大值
            if(type == 0 && dist[v] > min(dist[u], w[v]) || type == 1 && dist[v] < max(dist[u], w[v]))
            {
                if(type == 0) dist[v] = min(dist[u], w[v]);
                else dist[v] = max(dist[u], w[v]);

                if(!st[v])
                {
                    q.push(v);
                    st[v] = true;
                }
            }

        }
    }
}

int main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m; // n个节点 m条道路

    for(int i = 1; i <= n; i++)
        cin >> w[i];

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    while(m--) // 
    {
        int a, b, c; cin >> a >> b >> c;
        AddEdge(h, a, b); 
        AddEdge(rh, b, a); 
        if(c == 2) AddEdge(h, b, a),  AddEdge(rh, a, b); 
    }

    
    spfa(h, dmin, 0);

    spfa(rh, dmax, 1);

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);

    cout << res << endl;

    return 0;
}